/**
 *
 * Titre du TP : TP2
 *
 * Nom  : NGUYEN
 * Prenom : Quang Hoang
 *
 * Remarques :
 */
#include<stdio.h>
#include<stdlib.h>
#include <sys/sysinfo.h>
#include "fifo.h"
#include "graph.h"

static GRAPH *G;
static fifo * myfifo; // fifo using in bfs
long max_dist = 0; // max distance from root
long far_node = 0; // furthest node

struct sysinfo myinfo;

long getFreeRam(){
	  sysinfo(&myinfo);
//	  printf("freeram: %ld\n", myinfo.freeram/1024);
	  return myinfo.freeram;
}


int sort(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}

long bfs(long v0, long * distance, long * pere){

	long subGraphSize = 1; //at least if self in the sub graph
	long i;
	long u;
	long v;

	fifo_clear(myfifo);

	fifo_add(myfifo, v0);

	pere[v0] = v0;

	while(fifo_empty(myfifo) != 0){
		u = fifo_extract(myfifo);
		for(i = 0; i < G->degrees[u] ; i++){
			v = G->links[u][i];
			if(pere[v] < 0){ //v non-visited
				fifo_add(myfifo, v);
				pere[v] = u;
				distance[v] = distance[u] + 1;
				subGraphSize++;
			}
		}
	}
	return subGraphSize;
}

//------------------ Upper Bound --------------------//

long upper_b(long *deg, long *parent, long *dist, long u){

  long x = 0; // local root node
  long y = 0; // neighbor nodes
  long i = 0;

  fifo_clear(myfifo);

  for(i = 0; i<G->n; i++){
    parent[i] = i;
    dist[i] = -1;
  }

  dist[u] = 0; // distance of root = 0
  fifo_add(myfifo, u);
  while(fifo_empty(myfifo) == 1){ // fifo is not empty
    x = fifo_extract(myfifo);
    for(i = 0; i < G->degrees[x]; i++) { // for all adjacence y of the node x
      y = G->links[x][i]; // y is an adjacence of x
      if(dist[y] == -1){
        dist[y] = 1 + dist[x]; // distance between y and root
        parent[y] = x;
        fifo_add(myfifo, y);
      }
    }
  }

  long v = 0;
  long *max1_subheight = malloc(G->n*sizeof(long));
  long *max2_subheight = malloc(G->n*sizeof(long));
  long *height = malloc(G->n*sizeof(long)); // height of nodes in a tree
  long *max_d = malloc(G->n*sizeof(long)); // max distance in a tree

  fifo_clear(myfifo);

  // calcul degree of each nodes in the tree
  for(i = 0; i < G->n; i++){
    if(parent[i] != i && dist[i] != -1){
      deg[parent[i]]++;
    }
  }

  for(i = 0; i < G->n; i++){
    if(deg[i] == 0 && dist[i] != -1){fifo_add(myfifo, i);} // push nodes with degree = 0 to fifo
  }

    while(fifo_empty(myfifo) == 1){ // while fifo is not empty
      v = fifo_extract(myfifo);
      if(parent[v] != v) { // v is not the top of the tree
      if(height[parent[v]] <= (height[v] + 1)) { // update the height if needed
          height[parent[v]] = height[v] + 1;
        }

	// update the 2 max subheights
        if((height[v]+1) >= max1_subheight[parent[v]]){
          max2_subheight[parent[v]] = max1_subheight[parent[v]];
  	  max1_subheight[parent[v]] = height[v] + 1;
        }
        else if((height[v]+1) >= max2_subheight[parent[v]]){
	  max2_subheight[parent[v]] = height[v] + 1;
        }

	// update the max distance in the tree
        if(max_d[v] >= max_d[parent[v]] && max_d[v] >= (max1_subheight[parent[v]] + max2_subheight[parent[v]])){
          max_d[parent[v]] = max_d[v];
	}
	else if((max1_subheight[parent[v]] + max2_subheight[parent[v]]) >= max_d[v] && (max1_subheight[parent[v]] + max2_subheight[parent[v]]) >= max_d[parent[v]]) {
          max_d[parent[v]] = (max1_subheight[parent[v]] + max2_subheight[parent[v]]);
	}

	deg[parent[v]]--;
	if(deg[parent[v]] == 0){
 	  fifo_add(myfifo, parent[v]);
	}
      }
      else {
        return max_d[v];
      }
    }

}



int main(int argc, char** argv){

//	long ramBefore = getFreeRam();

	// check for nbr of arguments passed
	FILE *f = fopen(argv[1], "r");
	FILE * pfile;

	long i,j;
	int loop = 30; //number of loops

	G = graph_from_file(f, atol(argv[2]));
	fclose(f);

	printf("Nbr nodes : %ld\nNbr links : %ld\n",G->n, G->m);

	//----------------- Initiate value ---------------//

	long N = G->n; // number of nodes in the file

	long * distance = malloc(N * sizeof(long));
	long * pere = malloc(N * sizeof(long));
	fifo mainfifo = fifo_create(N);
	myfifo = &mainfifo;

	long * tree_deg = malloc(N * sizeof(long)); // degree of nodes in a tree
	long * order_deg = malloc(N * sizeof(long));
	long cSize, root, center=0; // (size, root) node of component
	long big = 0; // size of the biggest component
	long upper_bound = 0; // upper bound
	int e = 1, tmp; // epsilon

	//----------------- Initiate value ---------------//
	long numComp = 0; // nbr of components of the graph

	for(i = 0; i < G->n; i++){
		pere[i] = -1; // node i non-visited
		distance[i] = 0;
		order_deg[i] = 0;
	}

	//----------------- Max component ---------------//
	for(i = 0; i < G->n; i++){
		if(pere[i] < 0){ // node i is not visited
			cSize = bfs(i, distance, pere); //new subGraph non-visited, root=i

			if(big < cSize) {
				big = cSize; // update the biggest component
				root = i; // update root node of the biggest component
			}
			numComp++; // increase the nbr of components
		}
	}
	printf("Biggest component:  root : %ld  size : %ld\n", root, big);

	//-------------- Find the diameter using upper & lower bound --------------//
	for(i = 0; i<N; i++){ // reset distance of nodes
		distance[i] = -1;
	}

	pfile = fopen("result_file.txt", "w+");

	//----- Find the first lower bound
	bfs(root, distance, pere); // bfs in the biggest component to find max distance (lower bound)

	for(i = 0; i<N; i++){
		if(pere[i] != i && distance[i] != -1){
			order_deg[pere[i]]++;
			if(order_deg[pere[i]] > order_deg[center]){
				center = pere[i];
			}
		}
	}
	printf("Find the first lower bound done, center=%ld\n",center);

	//----- Find the first upper bound
	upper_bound = upper_b(tree_deg, pere, distance, center); // begin to find upper bound
	printf("lower bound: %ld upper bound: %ld\n", max_dist, upper_bound);
	fprintf(pfile, "%d %ld %ld\n", 0, max_dist, upper_bound); // print result to file

	for(j = 0; j < loop; j++){ // repeat to update max upper,lower bound
		order_deg[center] = 0;

		for(i = 0; i<N; i++){ // reset distance of nodes
			distance[i] = -1;
			if(order_deg[center] < order_deg[i]) {center = i;}
		}

		bfs(far_node, distance, pere); // find lower bound

		tmp = upper_b(tree_deg, pere, distance,center ); // find tempo upper bound
		if(upper_bound > tmp) {upper_bound = tmp;}
		printf("lower bound: %ld upper bound: %ld\n", max_dist, upper_bound);
		fprintf(pfile, "%ld %ld %ld\n", j+1, max_dist, upper_bound); // print result to file

		if(upper_bound - max_dist < e) {// exit if upper bound - lower bound < epsilon
			fclose(pfile);
			break;
		}
	}


	free(pere);
	free(distance);
	free(order_deg);
	free(tree_deg);

  return 0;
}

